1. Technical Field
This disclosure pertains in general to distributed computing and in particular to using a distributed computing system to find a path between nodes of a graph.
2. Background Information
In graph processing, a computing problem is represented by a graph having a set of vertices connected by a set of edges. The edges may have associated weights indicating, e.g., a distance represented by the edge or a cost incurred by traversing the edge. The graph can be used, for example, to model a real-world condition, and then the graph processing can act on the graph to analyze the modeled condition. For example, the World Wide Web can be represented as a graph where web pages are vertices and links among the pages are edges. In this example, graph processing can analyze the graph to provide information to a search engine process that ranks search results. Similarly, a social network can be represented as a graph and graph processing can analyze the graph to learn about the relationships in the social network. Graphs can also be used to model transportation routes, paths of disease outbreaks, citation relationships among published works, and similarities among different documents.
The single source shortest path problem is the problem of finding the shortest path between a single source vertex and every other vertex in a graph. For example, if a graph represents a road network a single source shortest path algorithm may seek to determine the shortest paths between a city and every other city in the graph. Conventional single source shortest path algorithms are implemented on a single system, use a single reference point, visit each vertex, and can only send messages between neighboring vertices. Conventional single source shortest path algorithms are slow in finding the shortest path in large graphs because they require traveling the diameter of the graphs.
For complex graphs, determining the shortest paths between vertices is a difficult problem and requires significant computing resources.